package com.wlr.study.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 恢复二叉搜索树
 *
 * @author lrwang
 * @version 1.0
 * @date 2022/4/5 23:02
 */
public class LeetCode99 {
    TreeNode t1, t2, pre;

    public void recoverTree(TreeNode root) {
        inorder(root);
        int temp = t1.val;
        t1.val = t2.val;
        t2.val = temp;
        System.out.println(root);
    }

    private void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        if (pre != null && pre.val > root.val) {
            if (t1 == null) {
                t1 = pre;
            }
            t2 = root;
        }
        pre = root;
        inorder(root.right);
    }


    public static void main(String[] args) {
        LeetCode99 leetcode99 = new LeetCode99();
        TreeNode root = new TreeNode(3);
        TreeNode rootLeft = new TreeNode(1);
        TreeNode rootRight = new TreeNode(4);
        TreeNode rootRl = new TreeNode(2);
        root.left = rootLeft;
        root.right = rootRight;
        rootRight.left = rootRl;
        leetcode99.recoverTree(root);
    }

}
